#ifndef DOUBLELIST_H
#define DOUBLELIST_H

#include <iostream>
#include <vector>
#include <functional>
#include <utility> 

class DoubleListNode;
using NodePtr = DoubleListNode*;

class DoubleListNode{
public:
	int val;
	NodePtr prev;
	NodePtr next;
	DoubleListNode() : val(0), prev(nullptr), next(nullptr){ }
	DoubleListNode(int value) : val(value) { }
	DoubleListNode(int value,NodePtr p, NodePtr n) : val(value), prev(p), next(n){ }
};
class DoubleList {
public:
	DoubleList() : head(nullptr){ }
	DoubleList(NodePtr h) : head(h){ }
	~DoubleList();
	//头插法
	void insertAtHead(int);
	
	//尾插法
	void insertAtTail(int);
	
	//计算链表长度
	int getSzie() const;
	
	//删除头节点
	void deleteAtHead();
	
	//删除指定值的节点
	void deleteValue(int);
	
	//删除尾节点
	void deleteAtTail();
	
	//删除指定位置节点
	void deleteAtPosition(int);
	
	//判空
	bool isEmpty() const{return head == nullptr;}
	
	//正向打印
	void printDllForward();
	
	//反向打印
	void printDllBackward();
	
	//查找并返回第一个特定值的节点
	NodePtr findFirst(int value);
	
	//查找并返回所有特定值的节点
	std::vector<NodePtr> findAll(int value);
	
	//查找指定位置的节点
	NodePtr getNodeAt(int position);
	
	//使用快慢指针，找寻中间节点
	NodePtr findMiddle();
	
	//判断链表是否为循环链表
	bool hasCircle();
	
	//查找环的入口节点（若存在环）
	NodePtr findCycleEntry();
	
	/*std::function<bool(int)> 是 C++ 中用于存储、传递和调用任意可调用对象
	（如函数、函数指针、lambda 表达式、仿函数等）的类型。它是 C++11 引入的标准库特性，属于函数式编程的一部分*/
	//查找第一个满足条件的节点
	NodePtr findFirstIf(std::function<bool(int)> condition);
	
	//查找所有匹配值的节点
	//返回值：包含所有值等于value的节点指针的向量，未找到则返回空向量。
	std::vector<NodePtr> findAllIf(std::function<bool(int)> condition);
	
	//获取节点的位置（索引）
	//返回值：节点在链表中的位置（从 0 开始），未找到则返回 - 1。
	int getPosition(NodePtr node);
	
	//判断节点是否存在于链表
	//返回值：存在返回true，否则返回false
	bool contains(NodePtr node);
	
	//判断值是否存在于链表
	//返回值：存在返回true，否则返回false。
	bool containsValue(int value);
	
	//查找最大值节点
	//返回值：值最大的节点指针，链表为空则返回nullptr。
	std::pair<NodePtr, int> findMax();
	
	//在链表头部进行批量插入
	void insertBatchAtHead(const std::vector<int>& values);
	
	//在链表尾部进行批量插入
	//预先构建一个子链表（由 values 中的元素组成）。
	//将该子链表与原始链表拼接（避免多次修改 head 指针）。
	void insertBatchAtTail(const std::vector<int>& values);
	
	/*插入排序（适合小规模数据）
	核心思想
	创建一个空临时链表 sortedList。
	遍历原链表的每个节点，将其按顺序插入到 sortedList 中。
	最后将 head 指向 sortedList。*/
	void sort();
private:
	NodePtr head;
};

#endif
